package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 92. 反转链表 II
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 * <p>
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 * <p>
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *
 * @author zjj_admin
 * @date 2022/11/18 17:05
 */
public class ReverseLinkedList2 {

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node6 = new ListNode(4, node5);
        ListNode node7 = new ListNode(3, node6);
        ListNode node8 = new ListNode(2, node7);
        ListNode node9 = new ListNode(1, node8);

        reverseBetween(node9, 2, 4);
    }


    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 39.3 MB
     * 击败
     * 42.22%
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left == right) {
            return head;
        }
        ListNode curr = head;
        //node1用于记录前面一段的最后一个节点
        ListNode node1;
        //node2用于记录后面一段的第一个节点
        ListNode node2 = new ListNode();
        //定义一个虚拟的头结点
        ListNode dummy = new ListNode();
        dummy.next = head;
        node1 = dummy;
        //dummy2的目的是为了在反转链表时方便插入操作
        ListNode dummy2 = new ListNode(-1000);
        //逆序后的头结点
        ListNode newHead = dummy2;
        //从第一个节点开始遍历，当遍历到 left 与 right时分别指定 node1 和 node2
        for (int i = 0; i < right; i++) {
            if (i < left - 1) {
                node1 = curr;
            }
            //当
            if (left - 1 <= i && i < right) {
                newHead = addNodeReverse(dummy2, curr);
            }
            curr = curr.next;
            node2 = curr;
        }
        //重新从head节点开始遍历
        curr = dummy;
        while (curr.next != null) {
            //当遍历到node1节点时
            if (curr == node1) {
                curr.next = newHead.next;
            }
            curr = curr.next;
        }
        //遍历结束之后将curr的next指针指向node2
        curr.next = node2;
        return dummy.next;
    }

    /**
     * @param head
     * @param node
     * @return
     */
    private static ListNode addNodeReverse(ListNode head, ListNode node) {
        ListNode node1 = new ListNode(node.val);
        //当头结点没有连接其他数据时，直接将节点添加到头结点后面即可
        if (head.next == null) {
            head.next = node1;
        } else {
            node1.next = head.next;
            head.next = node1;
        }
        return head;

    }
}
